package 常用集合与排序;

import java.util.Deque;
import java.util.LinkedList;

public class DequeTest {

    /**
     * 预设-1值
     * 记这种写法就行，这种写法更通用
     *
     * @param heights
     */
    public void 单调栈(int[] heights) {
        Deque<Integer> stack = new LinkedList<Integer>();
        // 注意这个-1不能乱设置，stack都是先pop再peek，会取到这个-1的
        stack.push(-1);

        for (int i = 0; i < heights.length; i++) {
            // 先决条件 && 破坏单调栈性质的数据（当前是个小值）
            // 反正我必须是里面最靓的仔
            while (stack.peek() != -1 && heights[i] <= heights[stack.peek()]) {
                // 长度
                int len = i - stack.peek();
                // heights[stack.peek()]的左边都是矮的，指望不上，右边一直到i都是高的，所以len直接乘上去
                //TODO 有长度了，该干嘛干嘛

                // 弹出
                stack.pop();
            }
            // 经过前面的处理，单调栈性质维护好了，把下标push进去
            stack.push(i);
//                System.out.println(stack.toString());
        }

    }


}
